package hot_100;

import java.util.*;

public class 分割回文串 {

    public static void main(String[] args) {
    }


    int n;
    char[] ch;
    String ss;
    boolean[][] vis = new boolean[17][17];
    List<List<String>> ans = new ArrayList<>();
    Deque<String> strings = new LinkedList<>();

    public List<List<String>> partition(String s) {
        n = s.length();
        ch = s.toCharArray();
        ss = s;
        for (boolean[] row : vis) {
            Arrays.fill(row, true);
        }
        for (int i = 2; i <= n; i++) {
            for (int st = 0; st + i - 1 < n; st++) {
                int ed = st + i - 1;
                if (vis[st + 1][ed - 1] && ch[st] == ch[ed])
                    vis[st][ed] = true;
                else
                    vis[st][ed] = false;
            }
        }
        Dfs(0);
        return ans;
    }

    public void Dfs(int x) {
        if (x == n) {
            ans.add(new LinkedList<>(strings));
        }
        for (int i = x; i < n; i++) {
            if (vis[x][i]) {
                strings.addLast(ss.substring(x, i + 1));
                Dfs(i + 1);
                strings.removeLast();
            }
        }
    }
}
